/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-25
 * Time: 21:21
 */

public class Solution {
    public boolean search(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        // 先恢复二段性, 即 递增的两段 以某个值作为分界 假如为 x, 左边这段 >= x, 右边这段 < x
        while (right > left && nums[right] == nums[0]) {
            right--;
        }
        // 后面要用到 right 提前记录一下
        int temp = right;
        // 第一次二分, 找到旋转点
        while (left < right) {
            int mid = ((right-left)>>1) + left;
            if (nums[mid] >= nums[0]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 最终 left 所在的位置就是旋转点

        // 然后以旋转点为边界, 对两边分别进行二分
        int ans = findTarget(nums, 0, left-1, target);
        if (ans != -1) {
            return true;
        }
        // 注意: 因为找旋转点时 right (右边界) 已经变化了, 所以要提前记录一下
        ans = findTarget(nums, left, temp, target);
        return ans != -1;
    }

    /**
     *  二分查找
     */
    private int findTarget(int[] nums, int left, int right, int target) {
        while (left < right) {
            int mid = ((right-left)>>1) + left;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
}
